package day02;

import java.util.HashMap;

// 5. 最长回文子串
public class No5 {
    /**
     * 查找字符串中最长的回文子串
     * 使用递归和记忆化搜索的方法，通过比较字符串首尾字符来判断回文性质
     * @param s 输入的字符串
     * @return 返回字符串s中的最长回文子串
     */
    static HashMap<String, String> map = new HashMap<>();
    public String longestPalindrome(String s){
        // 处理空字符串或null的情况
        if(s == null || s.length() == 0 ) return "";

        // 单个字符本身就是回文
        if(s.length() == 1) return s;

        char head = s.charAt(0);
        char tail = s.charAt(s.length()-1);

        // 如果已经计算过该子串，直接从缓存中获取结果
        if(map.containsKey(s)) return map.get(s);

        // 处理长度为2的字符串
        if(s.length() == 2){
            if(head == tail){
                return s;
            }else{
                return head+"";
            }
        }

        String re = "";

        String reNow = "";
        // 如果首尾字符相同，则递归检查内部子串
        if(head == tail){
            reNow = longestPalindrome(s.substring(1,s.length()-1));
            // 如果内部子串加上首尾字符能构成完整回文，则组合成结果
            if(reNow.length()+2 == s.length()) reNow = head + reNow + tail;
        }
        // 分别计算去掉首字符和去掉尾字符的子串的最长回文
        String reLeft = longestPalindrome(s.substring(0,s.length()-1));
        String reRight = longestPalindrome(s.substring(1,s.length()));
        // 比较三种情况的结果，取最长的
        re = reLeft.length() > reRight.length() ? reLeft : reRight;
        re = re.length() > reNow.length() ? re : reNow;

        // 将计算结果存入缓存
        map.put(s, re);
        return re;

    }

    /**
     * 使用动态规划算法查找字符串中最长的回文子串
     *
     * @param s 输入的字符串
     * @return 返回字符串中最长的回文子串
     */
    public String longestPalindrome2(String s){
        // 动态规划
        int len = s.length();
        if (len < 2) return s;

        // 创建二维DP数组，dp[i][j]表示从索引i到j的子串是否为回文
        boolean[][] dp = new boolean[len][len];
        // 单个字符都是回文
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        int maxLen = 1;
        int begin = 0;
        // 填充DP表，按列填充
        for (int j = 0; j < len; j++) {
            for (int i = 0; i < j; i++){
                // 长度为2的子串：直接比较两个字符
                // 长度大于2的子串：比较首尾字符且中间子串也是回文
                if (i+1 == j) dp[i][j] = (s.charAt(i) == s.charAt(j));
                else dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i+1][j-1];
                // 更新最长回文子串的信息
                if (dp[i][j] && j-i+1 > maxLen) {
                    maxLen = j-i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin+maxLen);
    }

}
